package dfs_bfs;

import java.util.*;

import org.junit.Test;

public class Ex621 {
    class Node {
        Character t;
        int lastUse;

        public Node (Character t, int lastUse) {
            this.t = t;
            this.lastUse = lastUse;
        }
    }
    class Solution {    
        //最初的版本错了，因为没有考虑应该去map-value最大的那个，导致到了最后还需要干等一波，很亏。
        public int leastInterval(char[] tasks, int n) {
            int[] ts = new int[26];
            Map<Character, Integer> map = new HashMap<>(); //记录时间
            for (char t: tasks) {
                ts[t - 'A']++;
                if (!map.containsKey(t)) map.put(t, 0);
            }
            return dfs(ts, n, map, tasks.length, 0);
        }

        public int dfs(int[] tasks, int n, Map<Character, Integer> map, int sum, int cur) {
            if (sum == 0) return cur;
            int res = Integer.MAX_VALUE;
            boolean cando = false;
            char c1 = '0';
            int max = Integer.MIN_VALUE;
            for (char c: map.keySet()) {
                if (map.get(c) <= 0 && tasks[c - 'A'] > 0) {
                    cando = true;
                    if (tasks[c - 'A'] > max) {
                        max = tasks[c - 'A'];//找到残余最大的那个完成
                        c1 = c;
                    }
                }
            }
            if (!cando) {
                for (char ch: map.keySet()) {
                    map.put(ch, map.get(ch) - 1);
                }
                res = dfs(tasks, n, map, sum, cur + 1);
            } else {
                map.put(c1, n + 1);
                    tasks[c1 - 'A']--;
                    for (char ch: map.keySet()) {
                        map.put(ch, map.get(ch) - 1);
                    }
                    res = dfs(tasks, n, map, sum - 1, cur + 1);
            }
            return res;
        }
    }

    //O(n)的解法：
    /* 
        木桶效应：所需的时间只与数量最多的几个任务与休息时间有关
        假设A的任务数量最多 'A','A','A', 'B','B','B','C','C','C','D','D','E'
        B、C和A一致
        若 n = 2按照 ABC ABC ABC， 将不会产生任何停顿
        对于多余的几个杂鱼，可以插到每个序列的后面， ABCD ABCD ABCE 
        但是这样会使得A的冷却时间“变长”。但是无论怎样，总耗时都是
        A的长度 * (冷却时间 + 1) + 额外杂鱼
        若杂鱼能插入到A的原冷却时间中，将不会有任何影响
        即使冷却时间**被占满了**，插入不了，也不会超过task.length的执行时间
        但是冷却时间没被占满，也会达到冷却时间被占满的时间

        =========================
        除了最后一桶可以消去冷却时间，其他各桶都必须有【等待下一桶】

    */
    class Solution2 {
        public int leastInterval(char[] tasks, int n) {
            int[] dic = new int[26];
            int maxTask = 0; //记录最长任务对应的字典序
            int t;
            for (char c : tasks) {
                dic[(t = c - 'A')]++;
                if (dic[maxTask] < dic[t]) maxTask = t;
            }

            //查看其他任务是否会超过A的冷却时间范围
            int width = 0;
            for (int i = 0; i < 26; i++) {
                if (dic[i] == dic[maxTask]) width++;
            }
            return Math.max(tasks.length, (dic[maxTask] - 1) * (n + 1) + width);
        }
    }

    @Test
    public void test() {
        char[] tasks = {'A','A','A', 'B','B','B'};
        // tasks = new char[] {'A','A','A', 'B','B','B','C','C','C','D','D','E'}; //["A","A","A","B","B","B", "C","C","C", "D", "D", "E"]
        int res = new Solution2().leastInterval(tasks, 2);
        System.out.println(res);
    }
}
